/**
 * @title 一，使用递归 
 * @step1 设定左中右三个端点，大小是从左到右
 * @step2 判断中点位子是不是在两端，是就在判断是不是是不是要找到值，
 * 是就返回。否则就输出‘不存在’。
 * @step3 判断中间位子是不是相等，大于的话，就往右边查找；否则就往左边查找。
 */
let count = 0//计数器
function dichotomy (arr, target, start = 0, mid = Math.floor((arr.length + start) / 2), end = arr.length) {
  count++
  if (mid <= 0 || mid >= arr.length - 1) {
    if (arr[mid] === arr[0]) return 0
    if (arr[mid] === arr[arr.length - 1]) return arr.length - 1
    return '不存在'
  }
  //递归调用的时候return，不能少，否则不会有返回值
  if (target === arr[mid]) {
    return '次数:' + mid
  } else if (target > arr[mid]) {
    return dichotomy(arr, target, start = mid, mid = Math.floor((end + mid) / 2), end)
  } else if (target < arr[mid]) {
    return dichotomy(arr, target, start, mid = Math.floor((mid + start) / 2), end = mid) 
  }
}
console.log(dichotomy([0, 1, 2, 3, 4, 5, 6, 7, 8], 0), '次数：' + count)

/**
 * @title 一，使用while循环,知道找到或者找遍历到了数组的端点。
 * @step1 设定左中右三个端点，大小是从左到右
 * @step2 判断中点位子是不是在两端，是就在判断是不是是不是要找到值，
 * 是就返回。否则就输出‘不存在’。
 * @step3 判断中间位子是不是相等，大于的话，就往右边查找；否则就往左边查找。
 */
